package com.LeeCode;

/**
 * 人口最多的年份
 */

public class Code1854 {
    public static void main(String[] args) {
        int[][] logs = {
                {1950, 1961}, {1960, 1971}, {1970, 1981}
        };
        System.out.println(new Code1854().maximumPopulation(logs));
    }

    public int maximumPopulation(int[][] logs) {
        int[] diff = new int[101];  // 映射 1950~2050

        for (int[] log : logs) {
            int birth = log[0], death = log[1];
            diff[birth - 1950]++;   // 出生年份开始 +1
            diff[death - 1950]--;   // 死亡年份开始 -1（死亡当年不计入）
        }

        int maxPop = 0;      // 最大人口数
        int ansIndex = 0;    // 最大人口对应的最小年份索引
        int currentPop = 0;  // 当前年份人口;

        for (int i = 0; i < 101; i++) {
            currentPop += diff[i];  // 前缀和，得到 1950+i 年的人口
            if (currentPop > maxPop) {
                maxPop = currentPop;
                ansIndex = i;
            }
        }

        return ansIndex + 1950;  // 转回真实年份
    }
}
